package offer;

import java.nio.charset.StandardCharsets;
import java.util.Arrays;

/**
 * @Author Elephas
 * @Date 2022/1/22
 **/
public class LongestPalindrome {
    public static void main(String[] args) {
        final String TEST_01 = "babad";
        new LongestPalindrome().longestPalindrome(TEST_01);
    }
    /*
        解法一：最长回文子串，暴力破解，时间复杂度o(n^2)，空间复杂度o(n) 可以优化至o(1)
     */
    public String longestPalindrome(String s){
        char strs[] = s.toCharArray();
        int maxLeft = 0,maxRight = 0,left,right;
        for (int i = 0; i < strs.length; i++) {
            left = right = i;
            while(left >= 0 && right <= strs.length - 1 ){
                if(strs[left] == strs[right]){
                    if(right - left >= maxRight - maxLeft){
                        maxLeft = left;
                        maxRight = right;
                    }
                    left--;
                    right++;
                }else{
                    break;
                }
            }
            left = i; right = i + 1;
            while(left >= 0 && right <= strs.length - 1 ){
                if(strs[left] == strs[right]){
                    if(right - left >= maxRight - maxLeft){
                        maxLeft = left;
                        maxRight = right;
                    }
                    left--;
                    right++;
                }else{
                    break;
                }
            }
        }
        return s.substring(maxLeft,maxRight);
    }

    /*
        解法二： Manacher 算法
     */
    /*
    public String longestPalindrome2(String s){
        String expandedString = expandString(s);
    }

     */
    public String expandString(String s){
        StringBuilder expandedString = new StringBuilder("#");
        for (int i = 0; i < s.length(); i++) {
            expandedString.append(s.charAt(i));
            expandedString.append("#");
        }
        return expandedString.toString();
    }
}
